package h0829;

import java.util.LinkedList;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 岛屿数量
 * @date 2024/8/29 19:55
 */
public class NumberOfIslands {
    public static void main(String[] args) {
        char[][] array = {
                {'0', '1', '0', '1'},
                {'1', '0', '1', '0'},
                {'0', '1', '1', '0'}
        };
        System.out.println(numIslands(array));
    }

    public static int numIslands(char[][] grid) {
        //行列
        int m = grid.length;
        int n = grid[0].length;

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(grid, m, n, i, j);
                }
            }
        }
        return ans;
    }

    private static void bfs(char[][] grid, int m, int n, int i, int j) {
        LinkedList<int[]> queue = new LinkedList<>();
        queue.addLast(new int[]{i, j});

        //bfs的过程中将字符设置为0
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int index = 0; index < size; index++) {
                int[] tmp = queue.removeFirst();
                int a = tmp[0];
                int b = tmp[1];
                //设置为0
                grid[a][b] = '0';

                //将上下左右加入队列
                if (a - 1 >= 0 && a - 1 < m && b >= 0 && b < n && grid[a - 1][b] == '1') {
                    queue.add(new int[]{a - 1, b});
                }
                if (a + 1 >= 0 && a + 1 < m && b >= 0 && b < n && grid[a + 1][b] == '1') {
                    queue.add(new int[]{a + 1, b});
                }
                if (a >= 0 && a < m && b - 1 >= 0 && b - 1 < n && grid[a][b - 1] == '1') {
                    queue.add(new int[]{a, b - 1});
                }
                if (a >= 0 && a < m && b + 1 >= 0 && b + 1 < n && grid[a][b + 1] == '1') {
                    queue.add(new int[]{a, b + 1});
                }
            }
        }
    }

    private static void dfs(char[][] grid, int m, int n, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, m, n, i - 1, j);
        dfs(grid, m, n, i + 1, j);
        dfs(grid, m, n, i, j - 1);
        dfs(grid, m, n, i, j + 1);
    }
}
